/**
 * com.future CO.,ltd.
 */

package com.future;

import java.util.HashMap;
import java.util.Map;

/**
 * 类说明：
 * 我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。
 * <p>
 * 你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。
 * <p>
 * 如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。
 * <p>
 * 拼出目标 target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/stickers-to-spell-word
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_minStickers_691 {

    public static void main(String[] args) {
        Solution_minStickers_691 minStickers691 = new Solution_minStickers_691();
        String[] stickers = {"with", "example", "science"};
        String target = "thehat";
        stickers = new String[]{"slave", "doctor", "kept", "insect", "an", "window", "she", "range", "post", "guide"};
        target = "supportclose";
        long s = System.currentTimeMillis();
        System.out.println(minStickers691.minStickers(stickers, target));
        long s2 = System.currentTimeMillis();
        System.out.println("minStickers1 耗时：" + (s2 - s));
        System.out.println(minStickers691.minStickers2(stickers, target));
        long s3 = System.currentTimeMillis();
        System.out.println("minStickers1 耗时：" + (s3 - s2));
    }

    /**
     * 答案没问题，但是超时，需要用动态规划
     *
     * @param stickers
     * @param target
     * @return
     */
    public int minStickers(String[] stickers, String target) {
        if (stickers == null || stickers.length == 0 || target == null || target.equals("")) {
            return -1;
        }
        int ans = p(stickers, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private int p(String[] stickers, String target) {
        if (target.length() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (String curStr : stickers) {
            String newTarget = minus(curStr, target);
            if (!newTarget.equals(target)) {
                int newRst = p(stickers, newTarget);
                min = Math.min(min, newRst);
            }
        }
        return min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min + 1;
    }

    private String minus(String curStr, String target) {
        int[] characters = new int[26];
        for (int i = 0; i < target.length(); i++) {
            characters[target.charAt(i) - 'a']++;
        }
        for (int i = 0; i < curStr.length(); i++) {
            characters[curStr.charAt(i) - 'a']--;
        }
        StringBuilder sb = new StringBuilder("");
        for (int c = 0; c < characters.length; c++) {
            if (characters[c] > 0) {
                for (int i = 0; i < characters[c]; i++) {
                    // 注意这里的，有多少个，都需要一个个拼接起来，比如aa,则count[0]=2,还原为："aa";
                    sb.append((char) (c + 'a'));
                }
            }
        }
        return sb.toString();
    }

    //===============================================优化
    public int minStickers2(String[] stickers, String target) {
        if (stickers == null || stickers.length == 0 || target == null || target.equals("")) {
            return -1;
        }
        int ans = p2(stickers, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private int p2(String[] stickers, String target) {
        Map<String, Integer> cache = new HashMap<>();
        if (target.length() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (String curStr : stickers) {
            int newRst;
            String newTarget = minus2(curStr, target);
            if (!newTarget.equals(target) && !cache.containsKey(newTarget)) {
                newRst = p(stickers, newTarget);
            } else {
                newRst = cache.get(newTarget);
            }
            min = Math.min(min, newRst);
        }
        return min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min + 1;
    }

    private String minus2(String curStr, String target) {
        int[] characters = new int[26];
        for (int i = 0; i < target.length(); i++) {
            characters[target.charAt(i) - 'a']++;
        }
        for (int i = 0; i < curStr.length(); i++) {
            characters[curStr.charAt(i) - 'a']--;
        }
        StringBuilder sb = new StringBuilder("");
        for (int c = 0; c < characters.length; c++) {
            if (characters[c] > 0) {
                for (int i = 0; i < characters[c]; i++) {
                    // 注意这里的，有多少个，都需要一个个拼接起来，比如aa,则count[0]=2,还原为："aa";
                    sb.append((char) (c + 'a'));
                }
            }
        }
        return sb.toString();
    }


}
